#ifndef SUBSEQUENCE_HPP_
#define SUBSEQUENCE_HPP_

#include <iostream>
#include <vector>
#include <map>

class Subsequence
{
public:
    Subsequence(/* args */){}
    ~Subsequence(){}

    std::vector<int> subsequence(std::vector<int> &num) {
        std::map< int, std::map< int, std::vector< int > > > map_dp;
        int result = INT32_MAX;
        std::vector<int> vct_result;

        for (int i = 0; i < num.size(); i++) {
            std::map<int, std::vector<int>> map_sum;

            for (int j = 0; j < i; j++) {
                if (num[j] >= num[i])
                    continue;

                auto sub = map_dp[num[j]];
                for (auto one : sub) {
                    if (one.first >= 200)
                        continue;

                    int sum = one.first + num[i];
                    std::vector<int> vct_subsequence =  one.second;
                    vct_subsequence.insert(vct_subsequence.end(), num[i]);

                    map_sum.insert(std::pair< int, std::vector< int > >(sum, vct_subsequence));
                    if (result > abs(sum - 200)) {
                        result = abs(sum - 200);
                        vct_result = vct_subsequence;
                    }
                }
            }

            std::vector<int> vct_subsequence = {num[i]};
            int sum = num[i];
            map_sum.insert(std::pair< int, std::vector< int > >(sum, vct_subsequence));
            if (result > abs(sum - 200)) {
                result = abs(sum - 200);
                vct_result = vct_subsequence;
            }
            map_dp.insert(std::pair< int, std::map< int, std::vector< int > > >(num[i], map_sum));
        }

        return vct_result;
    }
};

#endif // !SUBSEQUENCE_HPP_